#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include "tree.h"

using namespace std;

void preOrder(Tree *node, vector<int> &myVec)
{
    if (!node)
        return;

    myVec.push_back(node->data);
    preOrder(node->left, myVec);  
    preOrder(node->right, myVec);  
}

void posOrder(Tree *node, vector<int> &myVec)
{
    if (!node)
        return;

    posOrder(node->left, myVec);  
    posOrder(node->right, myVec);  
    myVec.push_back(node->data);
}

void inOrder(Tree *node, vector<int> &myVec)
{
    if (!node)
         return;

    inOrder(node->left, myVec);  
    myVec.push_back(node->data);
    inOrder(node->right, myVec);  
}

Tree *reconstruct(int inOrder[], int size1, int preOrder[], int size2)
{
    int index = 0;
    if (size1 <= 0) return NULL;

    Tree *node = new Tree(preOrder[0]);
    for (index = 0; index < size1; index++) {
        if (inOrder[index] == preOrder[0]) break;
    }
   
    node->left = reconstruct(inOrder, index, preOrder+1, index);
    node->right = reconstruct(inOrder+index+1, size1 - index-1, preOrder+index+1, size1-index-1);
    return node;
}

int count2 = 0;

/* reconstruct tree from inorder and posorder traverse*/
Tree *reconstruct2(int inOrder[], int size1, int posOrder[], int size2)
{
    int index = size2-1;
    if (size1 <= 0) return NULL;
    Tree *node = new Tree(posOrder[size2-1]);
    for (index = 0; index < size1; index++) {
        if (inOrder[index] == posOrder[size2-1]) break;
    }
    cout << size2 << " " << node->data << endl;
    count2++;
    if (count2%100 == 0) getchar();   
    node->left = reconstruct2(inOrder, index, posOrder, index);
    node->right = reconstruct2(inOrder+index+1, size1 - index-1, posOrder+index, size1-index - 1);
    return node;
}

int main(int argc, char **argv)
{
    int input[] = {7,5,6,3,2,8,10,11,35,56};
    Tree *root = NULL, *root2 = NULL;
    vector<int> inVec;
    vector<int> preVec;
    vector<int> posVec;
    int in[10], pre[10], pos[10];

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i]);
    }

    print_ascii_tree(root);

    preOrder(root, preVec); 
    for (int i = 0; i < preVec.size(); i++) {
        pre[i] = preVec[i];
        cout << preVec[i]  << " ";
    }

    cout << endl;

    inOrder(root, inVec); 
    for (int i = 0; i < inVec.size(); i++) {
        in[i] = inVec[i];
        cout << inVec[i]  << " ";
    }
    cout << endl;

    posOrder(root, posVec); 
    for (int i = 0; i < posVec.size(); i++) {
        pos[i] = posVec[i];
        cout << posVec[i]  << " ";
    }

    cout << endl;
    root2 = reconstruct2(in, inVec.size(), pos, posVec.size());

    print_ascii_tree(root2);
}
